package lib

//link to 44
//*可以匹配0或任意个*前面那个字符
func init() {
	Probs = append(Probs, Problem{
		Num:         10,
		Discription: "正则表达式匹配",
		Level:       3,
		Labels: map[string]int{
			"动态规划": 1,
		},
	})
}

func IsMatch2(s string, p string) bool {
	m := len(s)
	n := len(p)
	dp := make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	for j := 1; j <= n; j++ {
		//dp[0][j-1]表示只匹配一个星号前面的字符，dp[0][j-2]表示连同星号前面那个字符一起不匹配
		dp[0][j] = p[j-1] == '*' && (dp[0][j-1] || dp[0][j-2])
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j-1] == '.' {
				dp[i][j] = dp[i-1][j-1]
				continue
			}

			if p[j-1] == '*' {
				//匹配一个或0个*前面的字符
				dp[i][j] = dp[i][j-1] || dp[i][j-2]
				if j-2 >= 0 {
					preCh := p[j-2]
					if preCh == '.' {
						//如果*前面是.：那么这两个字符串可以匹配任意s[k:i]中任意多个字符
						//所以从dp[0,j-2]到dp[i,j-2]，只要有一个true，dp[i][j]就是true
						for k := i; k >= 0; k-- {
							if dp[k][j-2] {
								dp[i][j] = true
								break
							}
						}
					} else {
						//如果*前面是正常的字符，则从k=i开始往前看，判断s[k-1]是否等于p[j-2]
						//等于的话|=dp[k-1][j-2]
						for k := i; k >= 1; k-- {
							if s[k-1] == preCh {
								dp[i][j] = dp[i][j] || dp[k-1][j-2]
							} else {
								break
							}
						}
					}
				}
				continue
			}

			dp[i][j] = s[i-1] == p[j-1] && dp[i-1][j-1]
		}
	}

	return dp[m][n]
}